package com.breeze.tree;

import java.util.HashSet;
import java.util.Set;

/**
 * 字典树，前缀树
 * // TODO:
 */
class Trie {
    private Node root = new Node();

    /**
     * Initialize your data structure here.
     */
    public Trie() {

    }

    /**
     * Inserts a word into the trie.
     */
    public void insert(String word) {
        int index = 0;
        boolean finish = false;
        Set<Node> children = root.children;
        while (!children.isEmpty() && !finish) {
            String tmp = word.substring(index);
            for (Node child : children) {
                String childStr = child.str;
                if (childStr.equals(tmp)) {
                    // 如果该节点还不是word，更新为word
                    if (!child.isWord) child.isWord = true;
                    finish = true;
                    break;
                } else if (childStr.startsWith(tmp)) {
                    // 需要分裂
                    // 移除当前节点
                    child.parent.removeChild(child);
                    // 创建分裂前缀节点
                    Node prefixNode = new Node(true, tmp, child.parent);
                    child.parent.addChild(prefixNode);
                    // 更新当前节点为后缀节点
                    child.str = childStr.replace(tmp, "");
                    // 后缀节点作为前缀节点的子节点
                    prefixNode.addChild(child);
                    finish = true;
                    break;
                } else if (tmp.startsWith(childStr)) {
                    // 继续在该子树上查找
                    children = child.children;
                    // 更新index
                    index = childStr.length();
                    break;
                } else if (!commonPrefix(tmp, childStr).isEmpty()) {
                    // 两者存在公共前缀，进行裂变
                    String commonPrefix = commonPrefix(tmp, childStr);
                    child.parent.removeChild(child);
                    Node commonNode = new Node(false, commonPrefix, child.parent);
                    child.parent.addChild(commonNode);
                    // 裂变的两个节点
                    Node child1 = new Node(true, tmp.replace(commonPrefix, ""), commonNode);
                    Node child2 = new Node(true, childStr.replace(commonPrefix, ""), commonNode);
                } else {
                    Node node = new Node(true, tmp, child.parent);
                    child.parent.addChild(node);
                    finish = true;
                    break;
                }

            }
        }
    }

    /**
     * Returns if the word is in the trie.
     */
    public boolean search(String word) {
        return false;
    }

    /**
     * Returns if there is any word in the trie that starts with the given prefix.
     */
    public boolean startsWith(String prefix) {
        return false;
    }

    public void forEach(Node node) {
        // TODO: 遍历
    }

    public static String commonPrefix(String s1, String s2) {
        int endIndex = 0;
        for (int i = 1; i <= s1.length(); i++) {
            if (!s2.startsWith(s1.substring(0, i))) {
                break;
            }
            endIndex = i;
        }
        return endIndex == 0 ? "" : s1.substring(0, endIndex);
    }

    static class Node {
        // 是否是单词
        boolean isWord;
        // 当前节点的字符串
        String str;
        // 父节点
        Node parent;
        // 子节点
        Set<Node> children = new HashSet<>();

        public Node() {
        }

        public Node(boolean isWord, String str, Node parent) {
            this.isWord = isWord;
            this.str = str;
            this.parent = parent;
        }

        void addChild(Node child) {
            children.add(child);
        }

        void removeChild(Node child) {
            children.remove(child);
        }
    }

    public static void main(String[] args) {
        Trie trie = new Trie();
        trie.insert("apple");
        System.out.println(trie.search("apple"));   // 返回 true
        System.out.println(trie.search("app"));     // 返回 false
        System.out.println(trie.startsWith("app")); // 返回 true
        trie.insert("app");
        System.out.println(trie.search("app"));     // 返回 true
    }
}